package Sort.SortTest;

import Algorithm.Sort.*;

import static Algorithm.Sort.Template.isSorted;
import static Algorithm.Sort.Template.show;

/**
 * 测试排序算法
 */
public class Test {

    public static void main(String[] args) {

        //String[] a = {"c", "s", "d", "n", "x", "i", "n", "g", "w", "e", "i", "s", "h", "e", "l", "l", "s", "o", "r", "t"};

        //初始化测试数组
        int testSize = 50000;//测试数组的大小
        Comparable[] a = null;
        int[] b = null;

        //测试排序算法
        //排序sortTime次求平均时间 包含生成随机数组花费的时间
        int sortTime = 100;
        //总时长 单位毫秒 /ms
        int totalTime = 0;
        for (int i = 0; i < sortTime; i++) {
            a = Template.getData(testSize);
            b = Template.getIntData(testSize);
            long startTime = System.currentTimeMillis();   //获取开始时间
            //排序(1)选择排序 测试100次 数组大小5000 平均44 42ms
            //SelectionSort.sort(a);

            //排序(2)插入排序 测试100次 数组大小5000 平均32 29ms
            //InsertionSort.sort(a);

            //排序(3)希尔排序 测试100次 数组大小5000 平均19 29 39ms
            //ShellSort.sort(a);

            //排序(4)冒泡排序 测试100次 数组大小5000 平均108ms 116ms 136ms
            // BubbleSort.sort(a);

            //排序(5) 快速排序 测试100次 数组大小5000 平均0ms 1ms ？？？
            //加大测试量 测试100次 数组大小50000 平均运行时间：10 14 15ms
            // QuickSort.sort(a, 0, a.length - 1);

            //排序(6) 归并排序 测试100次 数组大小5000 18ms 11ms 10ms 16ms 13ms
            //一次性分配空间 0ms 1ms
            //加大测试量 测试100次 数组大小50000 平均运行时间：10ms 11ms 8ms 18ms 12ms
            //MergeSort.sort(a);

            //排序(7) 基数排序 测试100次 数组大小5000 平均运行时间：0ms
            // 加大测试量 测试100次 数组大小50000 5ms
            //用法二
            // 数组大小50000 平均运行时间：7ms 13ms 6ms 11ms
            // 测试100次 数组大小5000 平均运行时间：1ms
            // 经典的空间换时间算法
            //RadixSort.sort(b,6);
            RadixSort.sort(b);



            long endTime = System.currentTimeMillis(); //获取结束时间
            totalTime += (endTime - startTime);
        }
        System.out.println("测试" + sortTime + "次 " + "数组大小" + testSize + " 平均运行时间：" + totalTime / sortTime + "ms");

        //assert isSorted(a);
        assert isSorted(b);//基数排序
        System.out.println("最后一次排序后");
        //show(a);
        show(b);//基数排序
    }
}
